# -*- coding: utf-8 -*-

# __date:       2021/7/29
# __author:     Yang Chao
# __function:

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        self.res = []
        self.singleStr('', 0, 0, n)
        return self.res

    def singleStr(self, s, left, right, n):
        if left == n and right == n:
            self.res.append(s)
        if left < n:
            self.singleStr(s + '(', left + 1, right, n)
        if right < left:
            self.singleStr(s + ')', left, right + 1, n)
